package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC132 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
    * @param 此题目参考了别人代码
    * 这是因为问题情况较为复杂
    * 未来需要再次复习此道题目
    * 很优雅的动态规划，极为经典
    * @return:
    */
    public class Solution {

        public int minCut(String s) {
            int len = s.length();
            // 特判
            if (len < 2) {
                return 0;
            }

            // 状态定义：dp[i]：前缀子串 s[0:i] （包括索引 i 处的字符）符合要求的最少分割次数
            // 状态转移方程：
            // dp[i] = min(dp[j] + 1 if s[j + 1: i] 是回文 for j in range(i))

            int[] dp = new int[len];
            // 2 个字符最多分割 1 次；
            // 3 个字符最多分割 2 次
            // 初始化的时候，设置成为这个最多分割次数

            for (int i = 0; i < len; i++) {
                dp[i] = i;
            }

            // 参考「力扣」第 5 题：最长回文子串 动态规划 的解法
            boolean[][] checkPalindrome = new boolean[len][len];
            for (int right = 0; right < len; right++) {
                // 注意：left <= right 取等号表示 1 个字符的时候也需要判断
                for (int left = 0; left <= right; left++) {
                    if (s.charAt(left) == s.charAt(right) && (right - left <= 2 || checkPalindrome[left + 1][right - 1])) {
                        checkPalindrome[left][right] = true;
                    }
                }
            }

            // 1 个字符的时候，不用判断，因此 i 从 1 开始
            for (int i = 1; i < len; i++) {
                if (checkPalindrome[0][i]) {
                    dp[i] = 0;
                    continue;
                }

                // 注意：这里是严格，要保证 s[j + 1:i] 至少得有一个字符串
                for (int j = 0; j < i; j++) {
                    if (checkPalindrome[j + 1][i]) {
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }
            return dp[len - 1];
        }
    }

    class Solution_fail {
        public int minCut(String s) {
            List<int[]> split = new ArrayList<>();
            split.add(new int[]{0, 0, 1});//left index, right index, weather successive.

            for (int i = 1; i < s.length(); i++) {
                char cur = s.charAt(i);
                boolean hasMerged = false;
                for (int j = 0; j < split.size(); j++) {
                    int[] point = split.get(j);
                    if (point[1] == point[0] && s.charAt(point[0]) == cur && j == split.size() - 2) {
                        point[1] = i;

                        int reIdx = split.size() - 1;
                        while (reIdx > j) {
                            split.remove(reIdx--);
                            point[2] = 0;
                        }
                        hasMerged = true;
                        break;
                    } else if (s.charAt(point[0]) == cur && point[2] == 1 && j == split.size() - 1) {
                        point[1] = i;
                        hasMerged = true;
                        break;
                    }
                }

                if (!hasMerged) {
                    split.add(new int[]{i, i, 1});
                }
            }

            return split.size() - 1;
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.minCut("aaabaa"));
    }

    public static void main(String[] args) throws Exception {
        LC132 an = new LC132();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
